// Created by WXX on 2021/12/24 20:56
#include <iostream>
#include <vector>
#include <algorithm>
#include <unordered_map>

using namespace std;

/**
 * 执行用时：20 ms, 在所有 C++ 提交中击败了97.17%的用户
 * 内存消耗：19.8 MB, 在所有 C++ 提交中击败了51.89%的用户
 */
#define x first
#define y second

typedef pair<int, int> PII;

class Solution {
public:
    int largestValsFromLabels(vector<int> &values, vector<int> &labels, int numWanted, int useLimit) {

        int n = values.size();
        vector<PII> q;
        for (int i = 0; i < n; i++) q.push_back({values[i], labels[i]});

        sort(q.begin(), q.end(), greater<PII>());

        int res = 0;
        unordered_map<int, int> cnt;
        for (int i = 0; i < n && numWanted > 0; i++) {
            if (cnt[q[i].y] < useLimit) {
                res += q[i].x;
                cnt[q[i].y]++;
                numWanted--;
            }
        }
        return res;
    }
};

int main() {

    vector<int> values = {5, 4, 3, 2, 1}, labels = {1, 1, 2, 2, 3};
    cout << Solution().largestValsFromLabels(values, labels, 3, 1) << endl;  // 9

    return 0;
}
